Link to this headingGCM

GCM is a Combination of Counter Mode (CTR) with a Message Authentication Code (MAC) using an algorithm GMAC.

Link to this headingSecurity

This provides both authentication and encryption.

  • Vulnerable to nonce Reuse
  • Might not be timing safe

https://github.com/SalusaSecondus/CryptoGotchas#aes-gcmgmac

Link to this headingZero Nonce

If the nonce is set to All Zeros then the first block of the encryption can leak the authentication key.
This is because the Authentication key is the encryption of zero data. Using XOR you can recover the keystream if you know the plaintext.

This does depend on how GCM creates its IVs. If the IV starts off at 1 then it is possible to over flow the counter and get all IV and counter to 0.

Example:

message = b"\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00" #Generate the GCM Key using the encryption_key and null data auth_key = aes.ecb_encryption(b"\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00") gmac = GMAC(auth_key) # IV is 96 bytes iv = bytes.fromhex("000000000000000000000000") #Encrypt plaintext in Counter Mode ciphertext = aes.ctr_encryption(iv, message) #Use the IV as Additional authenticated data (AAD) #So if the iv changes then the tag changes tag_iv = gmac.digest(b"", ciphertext) #Then Encrypt the new data with the tag = aes.ctr_encryption(tag_iv, tag) print(f"auth_key: {auth_key.hex()}, tag_iv: {tag_iv.hex()}, iv: {iv.hex()}, ciphertext: {ciphertext.hex()}, tag: {tag.hex()}") #auth_key: aa1908ba6ab97a18ea6349b72eb1ba15, tag_iv: 00000000000000000000000000000000, iv: 000000000000000000000000, ciphertext: aa1908ba6ab97a18ea6349b72eb1ba15, tag: d387e6b9293ead8758976e85dd9e064b

GCM Nonce

Link to this headingStatic/Repeated IV

Since AES-GCM encrypts the message by XORing it with the output of AES-CTR, a duplicate nonce will result in identical AES-CTR output. If you know a plaintext and the ciphertext of one message then you can decrypt the other message

Duplicate Keystream:

message = b"Cool new message that" message2 = b'This is a testMessage' #Initialize AES Key #encryption_key = os.urandom(16) encryption_key = bytes.fromhex("bb98a1ffb3ece7a0a284cb5f5cd748ec") aes = AES(encryption_key) #Do AES GCM for message 1 iv, ciphertext, tag = aes_gcm(aes, bytes.fromhex("4ff34dcd6d2738f70bdab5f7"), message) print(f"iv: {iv.hex()}, ciphertext: {ciphertext.hex()}, tag: {tag.hex()}") #iv: 4ff34dcd6d2738f70bdab5f7, ciphertext: 9c4f37ccd0f521bd2dc4437ebe0c1a0b87e909a6dc, tag: 11944bc91a02aaf0b72b3f1b06d6d207 #### Do AES GCM for message 2 #Do AES GCM for message 1 iv2, ciphertext2, tag2 = aes_gcm(aes, bytes.fromhex("4ff34dcd6d2738f70bdab5f7"), message2) print(f"iv: {iv2.hex()}, ciphertext: {ciphertext2.hex()}, tag: {tag2.hex()}") #iv: 4ff34dcd6d2738f70bdab5f7, ciphertext: 8b4831d3d0f237ea6c895268be19300bd4ee00a0cd, tag: 9d316f98882a5cf704a2e5d6bdf44474 #### XOR the known plaintext to get the keystream data keystream = fixedlen_xor(ciphertext, b"Cool new message that") print(f"Keystream: {keystream.hex()}") #Keystream: df2058a0f09b44ca0da9260dcd6d7d6ea79d61c7a8 #### XOR The keystream data to get the unknown message2 plaintext = fixedlen_xor(ciphertext2, keystream) print(f"plaintext: {plaintext}") #plaintext: b'This is a testMessage' assert plaintext == message2

Source
Nonce-Disrespecting Adversaries: Practical Forgery Attacks on GCM in TLS

Link to this headingForgery Attacks with nonce Reuse

When an IV is Reused with a different message or aad it can be used to recover the GMAC secret. Using this Secret you can forge messages

Example Code

""" VolgaCTF Quals 2018 forbidden crypto task This implements the forbidden attack on Galois/Counter Mode AES useage: sage -python forb_expl.py """ from binascii import unhexlify, hexlify from sage.all import * from cryptography.hazmat.backends import default_backend from cryptography.hazmat.primitives.ciphers import ( Cipher, algorithms, modes ) def encrypt(iv, key, plaintext, associated_data): encryptor = Cipher( algorithms.AES(key), modes.GCM(iv), backend=default_backend() ).encryptor() encryptor.authenticate_additional_data(associated_data) ciphertext = encryptor.update(plaintext) + encryptor.finalize() return (ciphertext, encryptor.tag) def decrypt(key, associated_data, iv, ciphertext, tag): decryptor = Cipher( algorithms.AES(key), modes.GCM(iv, tag), backend=default_backend() ).decryptor() decryptor.authenticate_additional_data(associated_data) return decryptor.update(ciphertext) + decryptor.finalize() def slice_and_pad(b_str, bsize=16): b_str += b"\x00" * (len(b_str) % bsize) return [bytearray(b_str[k:k+bsize]) for k in range(0, len(b_str), bsize)] def unhex_blocks(h_str, bsize=16): if len(h_str) %2 != 0: h_str = "0" + h_str h_str = unhexlify(h_str) return slice_and_pad(h_str, bsize) def xor(a, b): assert(len(a) == len(b)) return bytearray([a[i] ^ b[i] for i in range((len(a)))]) def byte_to_bin(byte): b = bin(byte)[2:] return "0" * (8 - len(b)) + b def block_to_bin(block): assert(len(block) == 16) b = "" for byte in block: b += byte_to_bin(byte) return b def bytes_to_poly(block, a): f = 0 for e, bit in enumerate(block_to_bin(block)): f += int(bit) * a**e return f def poly_to_int(poly): a = 0 for i, bit in enumerate(poly._vector_()): a |= int(bit) << (127 - i) return a def poly_to_hex(poly): return (hex(poly_to_int(poly))[2:]).upper() def recover_mac_key(authed_plaintext1, authed_plaintext2, authed_plaintext3, ciphertext_1, ciphertext_2, ciphertext_3, tag1, tag2): # Assuming aad1 == aad2 and len1 == len2 # => (tagA + tagB) = ( CTA[0] x CTB[0]) * H ** 2 # => H ** 2 = (tagA + tagB) * Inv( CTA[0] x CTB[0]) # => H = sqrt((tagA + tagB) * Inv( CTA[0] x CTB[0])) assert len(authed_plaintext1) == len(authed_plaintext2) assert len(ciphertext_1) == len(ciphertext_2) plantext_length = (len(ciphertext_1) // 2) * 8 authed_planetext_len = len(authed_plaintext1) * 8 length_block = unhex_blocks(hex((authed_planetext_len << 64) | (plantext_length * 8))[2:-1]) ciphertexts = [ xor(ct1, ct2) for ct1, ct2 in zip(ciphertext_1, ciphertext_2) ] tags = xor(tag1, tag2) authed_plaintext = [ xor(ct1, ct2) for ct1, ct2 in zip(authed_plaintext1, authed_plaintext2) ] F, a = GF(2**128, name="a").objgen() R, H = PolynomialRing(F, name="H").objgen() #Set up f1 #f1 = A1_p * H**5 + C1_p[0] * H**4 + C1_p[1] * H**3 + C1_p[2] * H**2 + L_p * H + T1_p f1 = bytes_to_poly(authed_plaintext1[0], a) for data in authed_plaintext1[1:]: f1 = f1 * H + bytes_to_poly(data, a) for data in ciphertext_1: f1 = f1 * H + bytes_to_poly(data, a) f1 = f1 * H + bytes_to_poly(length_block[0], a) f1 = f1 * H + bytes_to_poly(tag1, a) #Setup F3 #f3 = A3_p * H**5 + C3_p[0] * H**4 + C3_p[1] * H**3 + C3_p[2] * H**2 + L_p * H f3 = bytes_to_poly(authed_plaintext3[0], a) for data in authed_plaintext3[1:]: f3 = f3 * H + bytes_to_poly(data, a) for data in ciphertext_3: f3 = f3 * H + bytes_to_poly(data, a) f3 = f3 * H + bytes_to_poly(length_block[0], a) f3 = f3 * H #Setup P #p = A_p * H**5 + C_p[0] * H**4 + C_p[1] * H**3 + C_p[2] * H**2 + T_p p = bytes_to_poly(authed_plaintext[0], a) for data in authed_plaintext[1:]: p = p * H + bytes_to_poly(data, a) for data in ciphertexts: p = p * H + bytes_to_poly(data, a) p = p * H p = p * H + bytes_to_poly(tags, a) keys = [] f_tags = [] for root, _ in p.roots(): keys.append(poly_to_hex(root)) EJ = f1(root) f_tags.append(poly_to_hex(f3(root) + EJ)) return keys, f_tags static_iv = bytes.fromhex("9315225df88406e555909c5aff5269aa") key = bytes.fromhex("9b43198e0832b5f8090f496f9384e91146816d22d51c4294cd4d3edc24d99597") ciphertext_1, tag_1 = encrypt(static_iv, key, b"From: John Doe\nTo: John Doe\nSend 100 BTC", b"John Doe") authed_plaintext1 = slice_and_pad(b"John Doe") ciphertext_2, tag_2 = encrypt(static_iv, key, b"From: VolgaCTF\nTo: VolgaCTF\nSend 0.1 BTC", b"VolgaCTF") authed_plaintext2 = slice_and_pad(b"VolgaCTF") ciphertext_3, tag_3 = encrypt(static_iv, key, b"From: John Doe\nTo: VolgaCTF\nSend ALL BTC", b"John Doe") authed_plaintext3 = slice_and_pad(b"John Doe") print(f"{ciphertext_1.hex()}, {tag_1.hex()}") print(f"{ciphertext_2.hex()}, {tag_2.hex()}") print(f"{ciphertext_3.hex()}, {tag_3.hex()}") cipher = Cipher( algorithms.AES(key), modes.ECB(), backend=default_backend() ).encryptor() output = cipher.update(b"\x00" * 16) + cipher.finalize() print(f"Auth Key: {output.hex()}") # tagA = (((((aad1 * H) + CTA[0]) * H) + len1) * H) + X # tagB = (((((aad2 * H) + CTB[0]) * H) + len2) * H) + X # tagA + tagB = ((((aad1 * H) + CTA[0]) * H) + len1) * H) + (((((aad * H) + CB1) * H) + len2) * H) + (X xor X) # = (aad1 * H^3 + CA1 * H^2 + len1 * H) + (aad2 * H^3 + CB1 * H^2 + len2 * H) # = (aad1 x aad2) * H^3 + (CA1 x CB2) * H^2 + (len1 x len2) * H # Assuming aad1 == aad2 and len1 == len2 # => (tagA + tagB) = ( CTA[0] x CTB[0]) * H ** 2 # => H ** 2 = (tagA + tagB) * Inv( CTA[0] x CTB[0]) # => H = sqrt((tagA + tagB) * Inv( CTA[0] x CTB[0])) auth_keys, forged_tags = recover_mac_key(authed_plaintext1, authed_plaintext2, authed_plaintext3, slice_and_pad(ciphertext_1), slice_and_pad(ciphertext_2), slice_and_pad(ciphertext_3), tag_1, tag_2) print(f"GMAC Key: {auth_keys}") print(f"Forged Tag: {forged_tags}") """ 368b81e98fe704c132229db5a2f2f61fc34cb88f1fd42e20904fc1a7d55c95740f0144978f224cda, e27ee66ab816204123cab7eb243ac616 368b81e98fe718c1362bdcb299d1f61fc34cb8931fd027619774e2a7d55c95740f005a968f224cda, 98c5ccf4ebce1cd2e2db5fc854a2dce4 368b81e98fe704c132229db5a2f2f61fc34cb8931fd027619774e2a7d55c95740f7138eb8f224cda, b04867e368349d384d963b5150d6660d Auth Key: 5d8f12b1723fad9cc6e60ad0258def6f GMAC Key: ['62771BC867FD0D2CF6144C43E3F4A15A', '5D8F12B1723FAD9CC6E60AD0258DEF6F'] Forged Tag: ['87A972FB4AE90C941E72E5E47A61DA36', 'B04867E368349D384D963B5150D6660D'] """

Link to this headingImplementation

Implications change depending on library

RFC

import os from aes_lib import AES from cryptopals_lib import fixedlen_xor, to_blocks, bytes_to_int, int_to_bytes class GMAC(): def __init__(self, authentication_key): self.length = 16 self.authentication_key = authentication_key def mult_Galios_Feild(self, y): """Multiply two polynomials in GF(2^m)/g(w) g(w) = w^128 + w^7 + w^2 + w + 1 (operands and result bits reflected)""" temp_key = bytes_to_int(self.authentication_key) y = bytes_to_int(y) z = 0 #print(temp_key,y,z) while y & ((1<<128)-1): if y & (1<<127): z ^= temp_key y <<= 1 if temp_key & 1: temp_key = (temp_key>>1)^(0xe1<<120) else: temp_key >>= 1 return z def xor_Mult_with_key(self, p,q): #print("p = {}, q = {}".format(p,q)) test = fixedlen_xor(p,q) #print("xor {}".format(test)) test = self.mult_Galios_Feild(test) test = int_to_bytes(test).rjust(self.length, b'\x00') #print("output {}".format(test)) #print() return test def gLen(self, s): #Get Byte length * 8 return (len(s) << 3).to_bytes(2, byteorder="big") def digest(self, additional_authenticated_data, input_data): output = b"\x00"*16 #Pad additional_authenticated_data additional_authenticated_data_padded = additional_authenticated_data + bytes((self.length-len(additional_authenticated_data)%self.length)%self.length) #print("Padded Authenticated Data: {}".format(additional_authenticated_data_padded)) #Pad Input Data input_data_padded = input_data + bytes((self.length-len(input_data)%self.length)%self.length) #print("Input Data: {}".format(input_data_padded)) #For each block of Padded additional_authenticated_data xor and mult with the auth key for aad_block in to_blocks(additional_authenticated_data_padded, self.length): output = self.xor_Mult_with_key(output, aad_block) #print("ADD OutputData: {}".format(input_data_padded)) #For each block of Padded input_data xor and mult with the auth key for input_block in to_blocks(input_data_padded, self.length): output = self.xor_Mult_with_key(output, input_block) #Also XOR and mult with the length of the data len_input = self.gLen(additional_authenticated_data) + self.gLen(input_data) return self.xor_Mult_with_key(output, len_input.rjust(self.length, b'\x00')) def aes_gcm(aes_obj, iv, message): #Generate the GCM Key using the encryption_key and null data auth_key = aes.ecb_encryption(b"\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00") gmac = GMAC(auth_key) # IV is 96 bytes if iv == None: iv = bytes.fromhex("4ff34dcd6d2738f70bdab5f7") #iv = os.urandom(16) # If tag is 96 bytes then shift and add 1 to make it 128 bits long # Else GMAC the IV if len(iv) == 12: tag_iv = iv + b"\x00\x00\x00\x01" else: tag_iv = gmac.digest(iv, b"") #Encrypt plaintext in Counter Mode ciphertext = aes.ctr_encryption(iv, message) #Use the IV as Additional authenticated data (AAD) #So if the iv changes then the tag changes tag = gmac.digest(b"", ciphertext) #Then Encrypt the new data with the tag = aes.ctr_encryption(tag_iv, tag) #print(f"auth_key: {auth_key.hex()}, tag_iv: {tag_iv.hex()}, iv: {iv.hex()}, ciphertext: {ciphertext.hex()}, tag: {tag.hex()}") return [iv, ciphertext, tag] if __name__ == '__main__': message = b"Cool new message that" #Initialize AES Key #encryption_key = os.urandom(16) encryption_key = bytes.fromhex("bb98a1ffb3ece7a0a284cb5f5cd748ec") aes = AES(encryption_key) #Do AES GCM for message 1 iv, ciphertext, tag = aes_gcm(aes, bytes.fromhex("4ff34dcd6d2738f70bdab5f7"), message) print(f"iv: {iv.hex()}, ciphertext: {ciphertext.hex()}, tag: {tag.hex()}") #iv: 4ff34dcd6d2738f70bdab5f7, ciphertext: 9c4f37ccd0f521bd2dc4437ebe0c1a0b87e909a6dc, tag: 11944bc91a02aaf0b72b3f1b06d6d207